import collections
from typing import List
from collections import Counter

from numpy import random


class Solution:

    def majorityElement(self, nums: List[int]) -> int:
        """
        哈希表
        """
        # n = len(nums)
        # i = n/2
        # map = {}
        # for num in nums:
        #     if num in map:
        #         map[num] += 1
        #     else:
        #         map[num] = 1
        #     if map[num] > i:
        #         return num
        """
        哈希表
        """
        # counts = collections.Counter(nums)
        # return max(counts.keys(), key=counts.get)
        """
        排序
        """
        # nums.sort()
        # return nums[len(nums) // 2]
        """
        随机化
        """
        majority_count = len(nums) // 2
        while True:
            candidate = random.choice(nums)
            if sum(1 for elem in nums if elem == candidate) > majority_count:
                return candidate


if __name__ == '__main__':
    nums = [3, 2, 3]
    print(Solution().majorityElement(nums))

    # c = Counter()
    # for i in 'sfsadfsdjklgsdla':
    #     c[i] += 1
    #
    # print(isinstance(c, Counter))  # True
    # print(isinstance(c, dict))  # True
    # print(c)  # Counter({'s': 4, 'd': 3, 'f': 2, 'a': 2, 'l': 2, 'j': 1, 'k': 1, 'g': 1})
    #
    # c2 = Counter('asfjslfjsdlfjgkls')
    # print(c2)  # Counter({'s': 4, 'd': 3, 'f': 2, 'a': 2, 'l': 2, 'j': 1, 'k': 1, 'g': 1})
